#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
#define ElementType int 
struct Node
{
    ElementType data;
    struct Node *next;
    struct Node *prev;
};
struct DoubleLinkList
{
    struct Node *head;
    struct Node *tail;
    int len;
};

typedef struct DoubleLinkList DLlist;

int InitDLinkList(DLlist *list)
{
    list->len=0;
    list->head=NULL;
    list->tail=NULL;
    return true;
}

struct Node *CreateNode(ElementType element)
{
    struct Node *newNode=(struct Node *)malloc(sizeof(struct Node));
    if(newNode==NULL)
    {
        printf("createNode malloc error!\n");
        return NULL;
    }

    newNode->data=element;
    newNode->next=NULL;
    newNode->prev=NULL;
    return newNode;
}

void InsertTail(DLlist *list, ElementType element)
{
    struct Node *newNode=CreateNode(element);
    if(newNode==NULL)
    {
        printf("insert CreateNode error!\n");
        return;       
    }
    if(list->len==0)
    {
        list->head=newNode;
        list->tail=newNode;
    }
    else
    {
        list->tail->next=newNode;
        newNode->prev=list->tail;
        list->tail=newNode;
    }
    list->len++;
}

void Travel(DLlist *list)
{
    printf("next: ");
    struct Node *TravelPoint=list->head;
    while(TravelPoint!=NULL)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint=TravelPoint->next;
    }
    printf("\n");

    printf("prev: ");
    TravelPoint=list->tail;
    while(TravelPoint!=NULL)
    {
        printf("%d ",TravelPoint->data);
        TravelPoint=TravelPoint->prev;
    }
    printf("\n");
}

void InsertIndex(DLlist *list, ElementType element, int index)
{
    if(index<0 || index>list->len)
    {
        printf("invalid space!\n");
        return;
    }

    struct Node *newNode=CreateNode(element);
    if(newNode==NULL)
    {
        printf("insertindex error!\n");
        return;
    }

    struct Node *TravelPoint=list->head;
    if(index==0)
    {
        newNode->next=TravelPoint;
        TravelPoint->prev=newNode;
        newNode->prev=NULL;
        list->head=newNode;
        list->len++;
        return;
    }

    // if(index==10)
    if(index==list->len)
    {
        TravelPoint=list->tail;
        TravelPoint->next=newNode;
        newNode->prev=TravelPoint;
        newNode->next=NULL;
        
        list->tail=newNode;
        list->len++;
        return;
    }

    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--;
    }
    struct Node *PrevNode=TravelPoint->prev;
    newNode->next=TravelPoint;
    newNode->prev=PrevNode;

    PrevNode->next=newNode;
    TravelPoint->prev = newNode;

    list->len++;
}

int main()
{
    DLlist list;
    InitDLinkList(&list);
    for(int i=0;i<10;i++)
    {
        InsertTail(&list,i+1);
    }
    Travel(&list);

    InsertIndex(&list,100,10);
    Travel(&list);
    return 0;
}